1. Field of the Invention
The present invention relates to a method and system for processing data having an index tree structure.
2. Description of the Related Art
In insertion and deletion of a record of data having an index tree structure, it is always necessary to increase a storage rate of records and decrease the number of orders of an index without rearranging the index. For this purpose, in inserting a record, a simple insert process, an overflow process, and a node split process have been performed. In deleting a record, a simple delete process, an underflow process, and a node concatenation process have been performed.
Data having an index tree structure and examples of the above processes will be described below with reference to FIGS. 1 to 8.
As shown in FIG. 1, an index tree is constituted by a group of nodes which are hierarchically arranged in a file storage unit (not shown). Each node includes a plurality of records and pointers, as shown in FIG. 2.
In a conventional data process, if an upper limit pointer count is set to be M, a lower limit pointer count m can be obtained by the following equation: EQU m=&lt;M/2&gt;
where &lt; &gt; represents that a decimal fraction is rounded up. In this case, a pointer count x of a predetermined node needs to be set to satisfy m.ltoreq.x .ltoreq.M.
In a simple insert process (see FIG. 3), if (a pointer count of a target node after insertion) .ltoreq.M, a pointer is inserted in the target node.
In an overflow process (see FIG. 4), if (a pointer count of a target node after insertion) &gt;M, and (a pointer count of an adjacent node) &lt;M, a predetermined number of records are moved from the target node to the adjacent node.
In a node split process (see FIG. 5), if (a pointer count of a target node after insertion) &gt;M, and (a pointer count of an adjacent node) =M, a new node is set, and the records of the target node and the adjacent node are split into the three nodes.
In a simple delete process (see FIG. 6), if (a pointer count of a target node after deletion) .gtoreq.m, a pointer is deleted from the target node.
In an underflow process (see FIG. 7), if (a pointer count of a target node after deletion) &lt;m, and (a pointer count of an adjacent node) &gt;m, a predetermined number of records are moved from the adjacent node to the target node.
In a node concatenation process (see FIG. 8), if (a pointer count of a target node after deletion) &lt;m, and (a pointer count of an adjacent node) =m, the target node and the adjacent node are concatenated into one node.
If an index tree is subjected to journal process, in order to decrease the journal amount and increase the efficiency of journal acquisition process, a change in index tree structure and the frequency of record movements between nodes due to a data process must be minimized. However, even if a difference in the number of records movement between a target node and its adjacent node is small, the above-described processes are performed.
For example, in a record insert process (M=50), if the pointer count of a target mode is 50 and that of an adjacent node is 49, an overflow process is performed. As a result, the pointer count of each of the target node and the adjacent node becomes 50. When another record is to be inserted in this target node, a node split process is performed. In this case, if a node split process is executed for the first record insert process, a change in index tree structure becomes smaller, and hence the journal amount is decreased.
Furthermore, in the conventional data process, if only a node split process is executed without performing an overflow, underflow, or node concatenation process, the journal amount can be reduced. However, one node may include only one pointer, and hence the storage rate of records is decreased.
As described above, in processing of records stored in a file storage unit, a demand has arisen for a data processing system which can reduce the journal amount by increasing the storage rate of records and decreasing the frequency of record movements between nodes.